package com.base.leetcode;

import com.base.dataStructure.Tree.TreeNode;

import java.util.Arrays;

/**
 * @Author: hdhao
 * @Create: 2023/4/5 - 20:35
 * @Version: v1.0
 */
//根据前序中序遍历结果构造二叉树
public class Leetcode105 {
    /*  根左右
        preOrder = {1,2,4,3,6,7}
        左根右
        inOrder = {4,2,1,6,3,7}

        根 1
        pre         in
        左 2,4       4,2
        右 3,6,7     6,3,7

        根 2
        左 4

        根 3
        左 6
        右 7
     */
    public TreeNode buildTree(int[] preOrder, int[] inOrder) {
        if (preOrder.length == 0 || inOrder.length == 0) {
            return null;
        }
        //创建根节点
        int rootValue = preOrder[0];
        TreeNode root = new TreeNode(rootValue);
        //区分左右子树
        for (int i = 0; i < inOrder.length; i++) {
            if (inOrder[i] == rootValue) {
                //0 - (i-1) 左子树
                //(i+1) -inOrder.length - 1 右子树
                //注意该拷贝方法的参数是含头不含尾的,左闭右开[ )

//                inOrder = {4,2,1,6,3,7}
                int[] inLeft = Arrays.copyOfRange(inOrder, 0, i);
                int[] inRight = Arrays.copyOfRange(inOrder, i+1, inOrder.length);
//                preOrder = {1,2,4,3,6,7}
                int[] preLeft = Arrays.copyOfRange(preOrder, 1, i + 1);
                int[] preRight = Arrays.copyOfRange(preOrder, i+1, preOrder.length);

                root.left = buildTree(preLeft,inLeft);
                root.right = buildTree(preRight,inRight);
                //找到根节点之后的操作不需要再切分递归,跳出循环
                break;
            }
        }
        return root;
    }
}
